#include <iostream>
#include <cmath>

using namespace std;

template<class T>
struct TREENODE
{
    T element;
    TREENODE<T>* lchild;
    TREENODE<T>* rchild;
    TREENODE()
    {
        lchild=rchild=NULL;
    }
    TREENODE(const T &data)
    {
        element=data;
        lchild=rchild=NULL;
    }
    TREENODE(const T &data,TREENODE* thelchild,TREENODE* therchild)
    {
        element=data;
        lchild=thelchild;
        rchild=therchild;
    }
};


template <class T>
class BINARYTREE
{
public:
    BINARYTREE(T data0);
    ~BINARYTREE();
    void insert(const T &element);
    void preprintf(const TREENODE<T>* root);
    void midprintf(const TREENODE<T>* root);
    void bacprintf(const TREENODE<T>* root);
    void clear(const TREENODE<T>* root);
    TREENODE<T>* root;
private:
    int capacity;
    int level;
    TREENODE<T>* tree;
    int k;
};

template<class T>
BINARYTREE<T>::BINARYTREE(T data0)
{
    root=(TREENODE<T>*)new TREENODE<T>;
    root->element=data0; 
    k=1;
};
template <class T>
 void BINARYTREE<T>::clear(const TREENODE<T>* root)
 {
     TREENODE<T>* origin=root->lchild;
     TREENODE<T>* originl=origin->lchild;
     while(originl!=NULL)
     {
         delete origin;
         origin=originl;
         originl=origin->lchild;
     }
     TREENODE<T>* originr=root->rchild;
     while(originr!=NULL)
     {
         delete origin;
         origin=originr;
         originr=origin->lchild;
     }
     delete root;     
 }


template<class T>
BINARYTREE<T>::~BINARYTREE()
{
    clear(root);   
};

template <class T>
void BINARYTREE<T>::insert(const T &element)
{
    TREENODE<T>* leaf=(TREENODE<T>*)new TREENODE<T>(element);
    if(leaf==NULL)
    {
        cout<<"the left can't create"<<endl;
    }
    TREENODE<T>* origin=root;

    if(k%2==1)
    {
        while(origin->lchild!=NULL)
        {
            origin=origin->lchild;
        }
        origin->lchild=leaf;
    }
    else
    {
        while(origin->rchild!=NULL)
        {
            origin=origin->rchild;
        }
        origin->rchild=leaf;
    }
    k++;
};


template<class T>
void BINARYTREE<T>::preprintf(const TREENODE<T>* root)  
{
    if (root!=NULL)
    {
        cout<<root->element<<"  ";
        preprintf(root->lchild);                
        preprintf(root->rchild);         
    }
};

template<class T>
void BINARYTREE<T>::midprintf(const TREENODE<T>* root)
{
    if (root!=NULL)
    {
        midprintf(root->lchild);
        cout<<root->element<<"  ";
        midprintf(root->rchild);
    }
};

template<class T>
void BINARYTREE<T>::bacprintf(const TREENODE<T>* root)
{
    if (root!=NULL)
    {
        cout<<root->element<<"  ";
        bacprintf(root->rchild);
        bacprintf(root->lchild);
    }
};


int main()
{
   BINARYTREE<int> a(0);
   for(int i=1;i<10;i++)
   {
       a.insert(i*3);
   }

   a.bacprintf(a.root);
   cout<<endl;
   a.midprintf(a.root);
   cout<<endl;
   a.preprintf(a.root);
   cout<<endl;

   system("pause");
   return 0;
}

// FIXME:
//  1. 可以先把程序写完，功能都正确之后在改进
//  2. 建议类的名字是`TreeNode`，全部都是大写的一般都是宏定义
//  3. `backprintf`等可以考虑如何更加通用，例如用户提供代码遍历过程的操作（例如打印）
//




        
